#选择排序

**原理**  /*
将数组第一个元素认为是有序数组，然后比较第二个元素的关键字与第一个元素关键字的大小，有序排列。
将数组后面一个元素的关键字插入到前面的有序数组中，一直重复至排序完成。

example: [4,2,1,3]
单次插入:  [4,2,1,3] > [1,4,2,3]
二次插入:  [1,4,2,3] > [1,2,4,3]
三次插入:  [1,2,4,3] > [1,2,3,4]
*/

**核心**  /*
将前i-1个元素当成排列好的序列，然后第i个元素如冒泡般逐步swap到合适的位置
*/

**我的实现**
vector<int> LySort::insertSort(vector<int> &v) {
    // 1.适当检查输入
    if (v.size() <= 1)
        return v;

    vector<int> out = v;
    // 2. 将前i-1个元素当成排列好的序列（开始指定为第0个元素为排列好的序列，所以i从1开始）
    for (int i=1; i<out.size(); ++i) {
        // 3. 拿出第i个元素，开始往前比较，小于则插到前一个元素前面
        for (int j=i; j>=1; --j) {
            if (out[j-1] > out[j])
                std::swap(out[j-1], out[j]);
        }
        // 4. 优化写法(减少j的循环，因为前面的序列一定是有序的，所以遇到更小的就不用想了)
        // for (int j=i; j>=1 && (out[j-1]>out[j]); --j) {
        //     std::swap(out[j-1], out[j]);
        // }
    }
    return out;
}

**思考** /*
时间复杂度分析：
在不考虑提前终止的情况下，
第一次内循环(j)比较1次，然后是2次，3次，……，最后一次内循环比较i-1次。
共比较的次数是 (i-1) + (i-2) + ... + 1，求等差数列和，得 (i- 1 + 1)*i / 2 = i^2 / 2。
取最高项系数，因此时间复杂度为 O(N^2)

空间复杂度分析：
耗费的空间与输入数据大小无关，无论输入数据增大多少倍，不会耗费额外的空间进行排序（除了数组本身的空间）
因此时间复杂度为 O(1)

稳定性分析：
稳定的关键，在于排序完成后，相同元素的相对顺序是否变化。
插入排序能否稳定，关键在于 if (out[j-1] > out[j]) 中使用 > 或者 >=
如使用 >= 则会在相同元素之间执行交换的操作，导致不稳定
而使用 >  则不会出现相同元素之间的交换，稳定！

泛化性分析：
冒泡排序适用从大量的元素中选择一部分排序元素，例如从10000个元素中选择出大小为前10的元素
此时，外循环只需要设置i<10，即可在结束后在序列的尾部10个元素得到目标值

*/

**进一步优化** /*
思考，既然前面的序列已经是有序的，而且需要在有序的序列中，查找一个位置
除了扫描一遍O(N)之外，是不是可以有O(logN)的方法 —— 二分查找法！
*/